The Internet has become established as an important part of our social infrastructure and besides conventional Best_Effort type data communications, starts to communicate data needed to ensure communication quality such as transaction data for mainstream business operations and audio-video. The volume of data being communicated is also increasing along with the spread of lines for accessing broadband communications by way of technology such as ADSL (Asymmetric Digital Subscriber Line) and FTTH (Fiber To The Home).
In order to acquire the communication status on the network in the environment described above, the carrier and ISP (Internet Service Provider) require a network monitoring function for collecting and analyzing statistics on the communication data volume on the network. Among this communication data, there is also a large need for a function for collecting and analyzing statistic information for each data group (hereafter flow) categorized into the data source and address, application and quality level, etc. By utilizing statistic information on each flow, the carrier and ISP can verify the quality assurance status when a communication quality assured service is provided. The carrier and ISP can also use limited network resources effectively to handle increased data volume using Traffic engineering (hereafter abbreviated to TE) technique. The carrier and ISP can also offer provisioning service which provides network resources speedily and timely to meet customer requests (bandwidth, quality of services), and can also detect and analyze network attacks, and can also carry out billing, etc.
A flow statistics collection method in the technology of the related art for example is the cache method (related technology 1). The related art 1 technology is made up of multiple statistics collection devices distributed within the network and a collector device for collecting statistic information periodically reported from these multiple statistics collection devices and analyzing traffic over the entire network. One example of a statistics collection device is a router that performs packet transfer in the network. Hereafter the processing by the statistics collection device in the related art is described using a router as an example.
When a packet is received, the router incorporating a statistic collection function searches a flow table in which one or more combinations (hereafter called flow conditions) of packet headers are stored (or registered) for identifying the flow. If the packet matches the stored flow conditions, then a 1 is added to the packet number stored for that matching flow conditions. The byte count of the received packet stored for that matching flow condition is also increased in the same way. If results from the search of the flow table show no matching flow condition, then the received packet header information combination is newly stored in the flow table. A search is made at fixed periodic intervals of each flow condition stored in the flow table and aging processing is performed to delete flow conditions whose statistic information is unchanged from the previous search. To delete a flow condition, a packet with the corresponding statistic information is generated and the packet sent to the collector device.
The number of bits for the search key in the flow table search is usually large compared to the number of bits of the search key for the destination search made when the router forwards a packet. Therefore, shortening the time needed for the flow table search is difficult compared to the destination search. This fact signifies that flow table search time takes up a large part of the router's packet processing time. The flow table search process therefore causes packet forwarding performance to deteriorate when flow table search time is larger than the required packet forwarding processing time.
In the related art technology 2, in order to alleviate the drop in packet forwarding performance due to the flow table search, routers containing high speed lines (ports) perform sampling of packets for flow table searches, according to a predetermined sampling rate and only make a flow table search of the sampled packets.
Though not a flow table search technology, a technology for making routing table searches was disclosed in JP-A No. 208945/2002 (Related technology 3). The related technology 3 utilizes a stored path table capable of spanning a first memory made up of high speed memories such as a Content Addressable Memory (CAM), and a second memory with a slower search speed than the first memory but possessing a higher degree of entry integration. The related technology 3 is capable of making entry searches requiring a larger number of bits than can be set in the CAM at higher speeds than when utilizing only a RAM (Random Access Memory).
[Patent document 1] JP-A No. 208945/2002
The above described related technologies 1 and 2 have the following problems when handing ever-increasingly large amounts of data, and in quality assurance of important data.
The search key for flow table that is a combination of multiple fields within the packet header has a larger number of bits compared to the search key for destination searches that is made up of only one field within the packet header or combinations of two fields. The number of flow conditions (hereafter, number of flow entries) stored in the flow table must also be several times larger than the number of entries in the destination table.
One method for searching tables comprised of multiple entries is a method (hereafter, Tree method) for storing flow tables in a tree structure in the memory by utilizing Dynamic Random Access Memory (DRAM) or Static Ram (SRAM) having an inexpensive cost per bit. Using the Tree method has the advantages that only a small number of memory chips are needed when storing information in a table made up of a large number of entries, the device has a low cost, and little installation space is needed in the device. However, multiple memory access lines are usually needed during a search so the search performance falls to only a fraction (less than a fifth or sixth) of that of the CAM method described next. So when search a flow table made up of a large number of entries, a device with a high line (circuit) speed will have a longer flow table search time than the allowable packet transmit time, due to time required for making the flow table search. The related art technology 1 that searches all received packets in a flow table, therefore cannot provide the required packet transmit performance.
The related art technology 2 provides the required packet transmit performance needed holding lines (port) with a high line speed by lowering the number of times flow table searches are made according to a preset sampling rate. This method performs packet sampling and is capable of finding statistical trends of each packet flow. However this method cannot acquire an accurate number of received packets or a received byte count. This method performs TE and provisioning, network facility planning, and attack detection by finding the statistical flow data size using the sample statistical value. Yet this method has problems because of use of sampling (sample statistical value) in cases for example where utilizing information shown by the network administrator to the network user regarding whether quality assurance is actually being performed on a network for a flow where quality assurance is needed, or when billing, where utilizing an accurate packet count or byte count is important.
One method for making high speed searches where the search key has a large number of bits is a search method using CAM (hereafter, called the CAM method). The CAM method is capable of high speed searches of search key bit patterns and bit patterns recorded in the memory. However, the cost per bit is high compared to typical memories. Other problems with the CAM method are that the number of CAM chips increases when dealing with large numbers of entries so that the device cost becomes higher, and the available mounting surface area inside the device is inadequate, etc. Yet another problem is that power consumption is high since all bit patterns registered in the memory and the search key bit pattern are compared in parallel.
The related art technology 3 discloses a method for high speed router searches of routing table. However it does not discuss flow table searches. In methods utilizing CAM and RAM, the time needed for accessing the RAM is added on to the time for the CAM method. Also, the same as with the Tree method when searching flow tables made up of a large number of entries in devices having lines (ports) with a high line speed, the time needed for searching the flow table becomes longer than the allowable packet forwarding processing time. In the related art technology 1 that searches all received packets in a flow table search, achieving the required packet processing performance is difficult